package tianhao.luo.algorithm;

/**
 * 希尔排序
 *
 * @author: tianhao.luo@hand-china.com 2021/6/18  14:06
 */
public class ShellSort {
    private int[] array;

    public ShellSort(int[] array) {
        this.array = array;
    }


    /**
     * 交换法实现排序
     */
    public void swapSort() {

        /*推导过程
        // 假设当前数组为:{8,9,1,7,2,3,5,4,6,0}
        // 第一轮排序:将10个数分为10/2=5组
        // 对这5组数据,每组按照步长5进行对应,并判断是否需要进行交换
        // 从第6个元素开始,找步长为5的有效数据;可知是要向前找对应的元素
        int temp=0;
        for (int i = 5; i < array.length; i++) {
            // 注意j的控制条件,j表示i对应的步长的元素,它可以为0;
            for (int j = i-5; j >=0; j = j-5) {
                // 判断是否需要进行元素交换?即j与j+步长的元素是否需要交换
                // array[j]<array[j+5]表示,从大到小排序
                // array[j]>array[j+5]表示,从小到大排序
                if (array[j]>array[j+5]){
                    temp = array[j];
                    array[j] = array[j+5];
                    array[j+5] = temp;
                }
            }
        }


        // 第二轮排序:将10个数分为5/2=2组
        // 对这2组数据,每组按照步长2进行对应,并判断是否需要进行交换
        // 从第3个元素开始,找步长为2的有效数据
        for (int i = 2; i < array.length; i++) {
            // 注意j的控制条件,j表示i对应的步长的元素,它可以为0;
            for (int j = i-2; j >=0; j = j-2) {
                // 判断是否需要进行元素交换?即j与j+步长的元素是否需要交换
                // array[j]<array[j+2]表示,从大到小排序
                // array[j]>array[j+2]表示,从小到大排序
                if (array[j]>array[j+2]){
                    temp = array[j];
                    array[j] = array[j+2];
                    array[j+2] = temp;
                }
            }
        }


        // 第三轮排序:将10个数分为2/2=1组
        // 对这1组数据,每组按照步长1进行对应,并判断是否需要进行交换
        // 从第2个元素开始,找步长为1的有效数据
        for (int i = 1; i < array.length; i++) {
            // 注意j的控制条件,j表示i对应的步长的元素,它可以为0;
            for (int j = i-1; j >=0; j = j-1) {
                // 判断是否需要进行元素交换?即j与j+步长的元素是否需要交换
                // array[j]<array[j+1]表示,从大到小排序
                // array[j]>array[j+1]表示,从小到大排序
                if (array[j]>array[j+1]){
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        */
        // 组数通过数组长度不断除2可得,直到grep ==0时,就表示排序完毕了
        for (int gap = array.length / 2; gap >= 1; gap = gap / 2) {
            int temp = 0;
            // 步长的控制,步长就等于组数
            for (int i = gap; i < array.length; i++) {
                // 注意j的控制条件,j表示i对应的步长的元素,它可以为0;
                for (int j = i - gap; j >= 0; j = j - gap) {
                    // 判断是否需要进行元素交换?即j与j+步长的元素是否需要交换
                    // array[j]<array[j+gap]表示,从大到小排序
                    // array[j]>array[j+gap]表示,从小到大排序
                    if (array[j] > array[j + gap]) {
                        temp = array[j];
                        array[j] = array[j + gap];
                        array[j + gap] = temp;
                    }
                }
            }
        }
    }

    /**
     * 移位法
     * <p>
     * 对交换法进行优化,不要发现不同就交换
     */
    public void moveSort() {

        // 组数通过数组长度不断除2可得,直到grep ==0时,就表示排序完毕了
        for (int gap = array.length / 2; gap >= 1; gap = gap / 2) {
            // 对每一组的元素进行插入排序
            for (int i = gap; i < array.length; i++) {
                // 待插入位置为有序表的最后一位,默认是步长gap前的元素,值为i-gap
                int insertIndex = i-gap;
                // 记录待插入元素值
                int insertValue = array[i];

                // insertIndex>=0 表示还可以继续向前找
                while (insertIndex >= 0 && insertValue < array[insertIndex]) {
                    // insertIndex索引的元素后移对应步长
                    array[insertIndex+gap] = array[insertIndex];
                    // 继续向前索引,需要是上一个步长的元素
                    insertIndex = insertIndex - gap;
                }
                // 向前找了一遍,发现自己就是最大的元素,则不需要移动
                // 存在小于自己的元素,才放入有序表中对应的位置
                if (insertIndex+gap != i){
                    array[insertIndex+gap] = insertValue;
                }
            }
        }
    }


    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}
